﻿// DetectLoop.cpp : Defines the entry point for the console application.


// Write the code, in a directed acyclic graph, print out all the element in the order that the child should be printed out before the parent is printed out.

/*

Algorithm: using an in-degree array
First, find a list of "start nodes" which have no incoming edges and insert them into a set S; 
at least one such node must exist in an acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)
*/

#include "stdafx.h"
#include <iostream>
#include <queue>
#include <stack>
using namespace  std;

void Print(int **p,int n)
{
    if(!p||n<=0) return;

    int *d=new int[n];

    for(int i=0;i<n;i++) 
        d[i]=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j&&p[i][j]>0) 
                d[j] += 1;

    stack<int> s,output;
    for(int i=0;i<n;i++)
    {
        if(!d[i]) 
            s.push(i);
    }

    for(int i=0;i<n;i++)
    {
        if(s.empty())
        {
            cout<<"Found cycle in DAG";
            return;
        }
        else
        {
            int v=s.top();
            s.pop();
            output.push(v);
            for(int j=0;j<n;j++)
            {
                if(v!=j&&p[v][j]) 
                    d[j]-=1;

                if(!d[j]) 
                    s.push(j);
            }
        }
    }

    while(!output.empty())
    {
        cout<<output.top()<<" ";
        output.pop();
    }
    delete []d;   
}

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}